package ch18._04;

import java.util.Map;
import java.util.HashMap;

public class Solution {
    public static int countOccurenceOfTwos(int n) {
	boolean negative = false;
	if (n < 0) {
	    negative = true;
	    if (n == Integer.MIN_VALUE) {
		return -1;
	    }
	    n = -n;
	}

	if (n < 2) {
	    return 0;
	}
	Map<Integer, Integer> memo = new HashMap<Integer, Integer>();
	int result = count(n, memo);
	return result;
    }

    private static int count(int n, Map<Integer, Integer> memo) {
	if (memo.containsKey(n)) {
	    return memo.get(n);
	}
	int result = 0;
	if (n < 2) {
	    result = 0;
	} else {
	    int mag = 1;
	    /**
	     * Good Question!
	     * Keep that in mind!
	     * Remember the overflow?? Use division instead.
	     * Or, use long instead of int.
	     */
//	    while (mag * 10 < n) {
	    while (mag < n / 10) {
		mag *= 10;
	    }
//	    if (n >= mag * 3) {
	    if (n / 3 >= mag) {
		result += mag;
//	    } else if (n >= mag * 2) {
	    } else if (n / 2 >= mag) {
		result += n - mag * 2 + 1;
	    }
	    result += count(n % mag, memo);
	    result += (n / mag) * count(mag, memo);
	}
	memo.put(n, result);
	return result;
    }

    public static void main(String[] args) {
		int n = 
				Integer.MAX_VALUE
				;
		int result = countOccurenceOfTwos(n);
		System.out.println(n);
		System.out.println(result);
	}
}